#include "DynamicArray.h"
#include "telephone.h"
struct DynamicArray
{
    ElementType *array; //数组指针
    int capacity;   //数组容量
    int size;       //元素个数
};

int GetSize(DArray *a)
{
    return a->size;
}

ElementType *GetArray(DArray *a)
{
    return a->array;
}

DArray *InitDArray()
{
    DArray *a = (DArray*)malloc(sizeof(DArray));
    if(a == NULL)
    {
        printf("InitDArray malloc error!\n");
        exit(-1);  //退出程序
    }
    a->size = 0;
    a->capacity = 10;
    a->array = (ElementType*)malloc(sizeof(ElementType) * a->capacity);
    if(a->array == NULL)
    {
        printf("InitDArray array malloc error!\n");
        exit(-1);
    }
    return a;
}

void InsertDArray(DArray *a,ElementType element)
{
    if(a->size == a->capacity)
    {
        a->capacity *= 2;
        a->array = (ElementType*)realloc(a->array,a->capacity * sizeof(ElementType));
        if(a->array == NULL)
        {
            printf("InsertDArray realloc error!\n");
            exit(-1);
        }
    }
    a->array[a->size++] = element;
}

void PrintDArray(DArray *a,void (*print)(ElementType))
{
    if(a->size < 1)
    {
        printf("通讯录为空!\n");
    }
    for(int i = 0; i < a->size; i++)
    {
        print(a->array[i]);
    }
}

ElementType FindByElement(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{
    for(int i = 0; i < a->size; i++)
    {
        if(compare(a->array[i],value))
            return a->array[i];
    }
    return NULL;
}

ElementType RemoveByIndex(DArray *a,int index)
{
    ElementType result = a->array[index];
    for(int i = index; i < a->size - 1; i++)
    {
        a->array[i] = a->array[i+1];
    }
    a->size--;
    return result;
}

ElementType RemoveDArray(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType))
{
    for(int i = 0; i < a->size; i++)
    {
        if(compare(a->array[i],value))
        {
            return RemoveByIndex(a,i);
        }
    }
    return NULL;
}

void MyFastSort(ElementType *a,int start,int end,bool (*compare)(ElementType, ElementType))
{
    if(start >= end)
        return ;
    int left = start;
    int right = end;
    ElementType temp = a[left];
    while(left < right)
    {
        while(compare(a[right],temp) && left < right)
            right--;
        if(left < right)
        a[left++] = a[right];

        while(compare(temp,a[left]) && left < right)
            left++;
        if(left < right)
        a[right--] = a[left];
    }
    a[left] = temp;

    MyFastSort(a,start,left - 1,compare);
    MyFastSort(a,right+1, end,compare);
}

void FastSort(DArray *a,bool(*compare)(ElementType,ElementType))
{
    MyFastSort(a->array,0,a->size - 1,compare);
}

ElementType BinarySearch(DArray *a,ElementType value,int(*compare)(ElementType,ElementType))
{
    int left = 0;
    int right = a->size - 1;
    while(left <= right)
    {
        int mid  = left + (right - left) / 2;
                //(left & right) + ((left ^ right)>>1);
        if(compare(a->array[mid],value) == 0)
        {
            return a->array[mid];
        }
        else if(compare(a->array[mid],value) > 0)
        {
            right = mid - 1;
        }
        else if(compare(a->array[mid],value) < 0)
        {
            left = mid + 1;
        }
    }
    return NULL;
}

void ClearDArray(DArray *a, void (*clear)(ElementType))
{
    if(a != NULL)
    {
        for(int i = 0; i < a->size; i++)
        {
            clear(a->array[i]);
        }
        free(a->array);
        free(a);
    }
}

void UpdateDArray(DArray *a,ElementType value,bool (*compare)(ElementType, ElementType),void(*update)(ElementType))
{
    int flag1 = 0, flag2 = 0;
    for (int i = 0; i < a->size; i++)
    {
        if (compare(a->array[i], value))
        {
            flag1++;
            flag2 = i;
        }
    }
    if (flag1 > 1)
    {
        for (int i = 0; i < a->size; i++)
        {
            char Num[Size];
            scanf("%s", Num);
            if (compare(a->array[i], Num))
            {
                update(a->array[i]);
                return;
            }    
        }
        return;
    }
    else if (flag1 == 1)
    {
        update(a->array[flag2]);
        return;
    }
}

void FindAllByElement(DArray *a, ElementType value, bool (*compare)(ElementType, ElementType), void (*print)(ElementType)) 
{
    int found = 0;
    for (int i = 0; i < a->size; i++) 
    {
        if (compare(a->array[i], value)) 
        {
            print(a->array[i]);
            found++;
        }
    }
    if (found == 0) 
    {
        printf("没有找到匹配的用户。\n");
    }
    else 
    {
        printf("共找到 %d 个匹配的用户。\n", found);
    }
}